/*
 * @lc app=leetcode.cn id=279 lang=javascript
 *
 * [279] 完全平方数
 */

// @lc code=start
/**
 * @param {number} n
 * @return {number}
 */
var numSquares = function(n) {
    let db=[0,1,2,3,1]
    for(let i=4;i<=n;i++){
        let min=Infinity
        for(let j=1;j*j<=i;j++){
            min=Math.min(db[i-j**2],min)
        }
        db[i]=min+1
    }
    return db[n]
};
// @lc code=end

